LuxSum 3 编译原理课设 C+Lucas Compiler

LuxSum 3 编译原理课设 C+Lucas Compiler

三月 30, 2019

test

编译原理课程设计/软件课程设计Ⅱ项目，用python写了一个类似于 C 和 Python 语法的所谓C+Lucas语言编译器，只包含词法分析和语法分析部分（语义分析没怎么听过课，不会写）。

编译器词法分析部分首先读取LAGrammer内的正规文法，完成从正规文法到NFA到DFA的转换，再根据DFA将读取的code.cpl转换为包含单词符号二元式的列表；语法分析部分首先读取SPGrammer内的二型文法，完成LR1分析后生成ACTION和GOTO表，从而对词法分析结果的输入串（单词符号集）进行分析，判断其是否被该文法接受。

C+Lucas语言简介

词法

支持运算符：binary_operator & unary_operator

双目：+ += - -= * *= / /= % %= & &= | |= ^ ^= < <= > >= = == != && ||

单目：+ ++ - -- ! ~

赋值运算符=可在词法分析时被识别，但在传送到语法分析时按原值表示。

支持类型：type

int float double char bool void string

支持关键字：keyword

return for while break continue if else

关键字可在词法分析时被识别，但在传送到语法分析时按原单词表示。

支持常量值：const

True False None

支持界符：limiter

( ) [ ] { } , ;

界符可在词法分析时被识别，但在传送到语法分析时按原值表示。

支持标识符：identifier

可由_和字母开头，由_和数字字母组成。

支持常量数：constnumber

支持符号数、小数、科学记数法（支持-0）。

支持常量字符字面量：constliteral

支持“xxx”类型的常量字符字面量值，支持\“转义；

支持'xxx'类型的常量字符字面量值，支持\'转义。

支持注释

支持以#开头的单行注释，遇到换行符\n停止。

语法

外部可以不断叠加external_declaration。

external_declaration

包含function_definition，declaration，comment，即最外层作用域可以存在函数定义，声明和注释。

function_definition

必须定义返回类型，标识符（函数名），参数可为空也可为多个，后跟compound_statement。

declaration

必须包含类型和=的直接赋值语句，句末应有;，类型后可以多次赋值。

statement

包含selection_statement，iteration_statement，jump_statement，compound_statement，declaration，comment， expression;。

selection_statement

没有elseif语句，只有if...和if...else...两类。

iteration_statement

for循环最左必须为declaration，中间和右侧为expression；

while循环条件为expression。

compound_statement

大括号包含多个语句。

expression

包含constant_expression和function_expression。

constant_expression

支持单目运算符在前的表达式、标识符、常量数字、常量字符字面值、常量和括号内表达式；

支持多次算术运算表达式。

编译器实现

整体结构

主体文件结构如下：

  • Definitions中存储C+Lucas的一些定义和预置模式，修改DEBUG值为True可进入DEBUG模式，输出显示具体信息；
  • LAGrammer中存储预置的正规文法，其内容代表了C+Lucas的词法定义，如单目运算符、双目运算符、关键词、数字常量、字面值常量等；
  • SPGrammer中存储预置的二型文法，其内容代表了C+Lucas的语法定义，如语法可包含函数定义和普通声明，语句包含选择语句、循环语句、跳转语句、复合语句、声明、注释、表达式等；
  • code.cpl中存储输入待分析的代码；
  • LexicalAnalyzer中存储进行词法分析的代码，包含正规文法预处理、正规文法转NFA、NFA转DFA、代码转换等函数，其读入LAGrammer、code.cpl文件，输出单词符号二元式列表；
  • SyntaxParser中存储进行语法分析的代码，包含二型文法预处理、获取NULL集、获取FIRST集、LR1项目集规范族的构造、获取LR1分析表、输入串分析等函数，其读入SPGrammer文件，接受LexicalAnalyzer输出，输出输入代码是否被接受【ACCEPT/ERROR】。

总体上，词法分析的主要难点在于通过子集法完成NFA到DFA的转换，而语法分析的主要难点在于LR1项目集规范族和分析表的构造，二者本质都是计算闭包和转换函数获取DFA。但在具体实现时，分别以面向过程和面向对象的风格完成了具有同样功能的函数的代码编写。以下为主要函数的实现分析。

词法分析

实现特点

NFA和DFA通过包含N状态列表、T字母表、F转换函数、S非空初态集、Z终态集的一个列表表示：[N, T, F, S, Z]。主要维护N的状态列表，每个状态集使用其在N中的序号列表表示。这里主要使用面向过程的思想解决了NFA和DFA的转换问题。

主体流程

主要函数实现

ep_closure

1
2
3
4
5
6
7
8
9
10
  def ep_closure(src, f):
...
      while len(queue):
          s = queue.pop(0)
          if s in f and '@' in f[s]:
              for tar in f[s]['@']:
                  if tar not in ans:
                      queue.append(tar)
                      ans.add(tar)
      return ans

计算状态集合src的ε闭包，表示为ε-closure(src)（实际是move函数的一种特殊情况）：

定义为一个状态集，是状态集src中的任意状态s经任意条ε弧而能到达的状态的集合。

这里使用队列模拟bfs搜索实现：维护一个队列和一个结果集合，队列初始化为src，当队列不为空时移出队列头s，根据转移函数判断s是否有经过ε弧到达的状态，如果有且不在结果集合内，加入队列和结果集合。

move

1
2
3
4
5
6
7
def move(src, f, ed):
    tar = set()
    for s in src:
        if s in f:
            if ed in f[s]:
                tar |= f[s][ed]
    return tar

计算状态集合src的ed弧转换，表示为move(src,ed)：

定义为状态集合tar，其中tar是所有那些可从src中的某一状态经过一条a弧而到达的状态的全体。

这里利用python内部集合运算来实现：判断src中某一状态s经过ed弧是否到达任何状态，如果是则加入集合tar中。由于tar是集合，具有无序性和唯一性，不需进行判断。

nfa2dfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  def nfa2dfa(N, T, F, S, Z):
...
      t = ep_closure(S, F)
      DN.append(t)
      queue.append(t)
      while len(queue):
          p = queue.pop(0)
          for a in T:
              tnext = ep_closure(move(p, F, a), F)
              if len(tnext) == 0:
                  continue
              if tnext not in DN:
                  DN.append(tnext)
                  queue.append(tnext)
              DF[DN.index(p)][a] = DN.index(tnext)
...

NFA转换为DFA的核心函数，其中NFA和DFA都通过包含N状态列表、T字母表、F转换函数、S非空初态集、Z终态集的一个列表表示：[N, T, F, S, Z]。

算法完全按照《编译原理》第51页的子集构造算法实现：通过维护一个队列来存储尚未被标记的子集p，当队列非空时，弹出队首p，标记之。对每个输入字母a，计算tnext=ep_closure(move(p, a))，当tnext非空且尚未被标记，将其加入队列中。

考虑到在进行ep_closure和move运算时，都是通过set数据类型完成操作，因此每个闭包都是由set类型维护，因此输出的DFA的N状态列表中存储的是多个set集合。而这里的转换函数是通过python中的dict数据类型（相当于C++ stl中的map）套dict维护的，dict中的key不能够是set这种unhashable的类型，因此这里最外层dict的key中存放的是set集合在N状态集合中的序号（通过index函数实现），第二个dict的key存放ed弧，第二个dict的val存放目标状态的序号：F[index][ed]=index。

scan

代码扫描转换函数，在一个始终执行的while循环中不断调用此函数，直到此函数返回END或ERROR为止，否则将函数返回的结果加入到结果列表中，最终的结果列表即为代码转换得到的单词符号二元式。

DFA识别的主体思想是：对每个DFA都进行一次识别，最终结果是识别到的最长的字符串和其DFA代表的类型的二元组。整体呈现一种贪心的思想，并根据LAGrammer中正规式的顺序体现各DFA的优先级。

具体实现如下：

  • 在每次的扫描过程中，维护通过getchar函数获得的源代码中的当前字母：curChar变量（如果当前字母为空格则获取下一字母，直到当前字母非空）。在进入DFA识别过程之前记录：

    • 识别得到的最长字符串：finalStr；

    • 识别得到的最终类型：finalType（初始化为undefine）；

    • 识别得到的最长字符串的最后字母的位置：finalPos；

    • 当前字母在源代码中的位置：curPos。

  • 进入DFA识别，首先将curChar初始化为curPos位置的字符，保证每个DFA识别相同串。当当前状态可以通过curChar弧跳转到下一状态时，将curChar加入维护的识别串中，跳转到下一状态，继续当前操作；

  • 如果跳转到了最终状态，判断当前DFA维护的识别串是否比finalStr串长，是则将其赋值给finalStr，并改变finalType和finalPos；

  • 所有DFA识别完成后，如果finalType仍为undefine，表明没有DFA可以识别当前代码，输出错误信息；否则返回[finalStr,finalType]，置当前源码读取位置为finalPos-1。

语法分析

实现特点

维护了一个Item类和ITEMLIST列表，使用初始项目实例化，类的内部可以自动计算项目集的闭包，每个类都用其在ITEMLIST中的序号表示。这里使用了偏向于面向对象的思想，解决了DFA的闭包计算和转换函数计算的问题。

主体流程

主要类实现

class Item

成员
  • prod：对初始项目集完成闭包计算后的项目集族；
  • next：后续建立的当前项目集族到下一项目集族的连接关系。
成员函数

  • get_closure(start)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def get_closure(self, start):
        ...
        while len(queue):
            lhs, rhs, la = queue.pop(0)
            pos = rhs.index('.')
            if pos < len(rhs) - 1:
                if rhs[pos + 1] in NONTERMINAL:
                    newla = get_lookahead(([] if pos == len(rhs) - 2 else rhs[pos + 2:]), la)
                    for plhs, prhs in PRODUCTION:
                        if plhs == rhs[pos + 1]:
                            if prhs == ['@']:
                                tmp = ['.']
                            else:
                                tmp = copy.deepcopy(prhs)
                                tmp.insert(0, '.')
                            if [plhs, tmp, newla] not in prod:
                                prod.append([plhs, tmp, newla])
                                queue.append([plhs, tmp, newla])
        ...

    计算状态集合start的闭包，表示为get_closure(start)：

    1. 假定I是一个项目集，I的任何项目都属于CLOSURE(I)；
    2. 若有项目A->α.Bβ,a属于CLOSURE(I)，B->γ是产生式，b∈FIRST(βa)，则B->.γ,b也属于CLOSURE(I)
    3. 重复CLOSURE(I)直到不增大为止。

    此处算法和ε-closure函数十分相似，只是多了一些细节处理，如lookahead计算和.的添加等，不多赘述。

主要函数实现

getNullable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def getNullable():
    change = True
    while change:
        change = False
        for [lhs, rhs] in PRODUCTION:
            if lhs not in NULLABLE:
                if rhs == ['@']:
                    NULLABLE.add(lhs)
                    change = True
                else:
                    nullable = True
                    for c in rhs:
                        nullable &= (c in NULLABLE)
                    if nullable:
                        NULLABLE.add(lhs)
                        change = True

getNullable函数计算出所有能够推导出ε的非终结符集合NULLABLE。

通过维护标志位change实现，在一个while change的循环中，遍历左部不在NULLABLE内的所有产生式，当其右部为ε或可以推出ε时将左部加入NULLABLE，并更改change状态再进行一轮循环。

这种类似于dfs的写法时间复杂度较高，可以被更快捷的记录路径型dfs写法替代，并非最优写法。

getFirst

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  def getFirst():
...
      def recur_get_first(tar):
          if tar in mem:
              return mem[tar]
          for [lhs, rhs] in PRODUCTION:
              if lhs == tar:
                  for c in rhs:
                      if c in TERMINAL:
                          FIRST[lhs].add(c)
                          break
                      elif c in NONTERMINAL:
                          recur_get_first(c)
                          FIRST[lhs] |= FIRST[c]
                          if c not in NULLABLE:
                              FIRST[lhs] -= {'@'}
                              mem[lhs] = copy.deepcopy(FIRST[lhs])
                              break
      for n in NONTERMINAL:
          recur_get_first(n)

getFirst函数计算出所有非终结符的First集，存储于First dict中。

这里通过典型的dfs实现，使用mem来维护计算完成的结果，以减少递归次数，优化算法。对于要求计算First集的非终结符，遍历所有以它为左部的产生式，遍历每个产生式右部，如果遇到终结符，加入First集并break，否则计算遇到的非终结符的First集，并将其加入到First集中。此外，只有右部可以推导出ε时First集才可出现ε。

LR1Parsing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  def LR1Parsing():
      it = Item([['<S>', ['.', '<start>'], {'#'}]])
...
      while len(queue):
          item = queue.pop(0)
          for lhs, rhs, la in item.prod:
              pos = rhs.index('.')
              if pos < len(rhs) - 1:
                  if rhs[pos + 1] not in mp.keys():
                      mp[rhs[pos + 1]] = []
                  tmp = copy.deepcopy(rhs)
                  tmp[pos], tmp[pos+1] = tmp[pos+1], tmp[pos]
                  mp[rhs[pos + 1]].append([lhs, tmp, la])
          for key in mp.keys():
              val = mp[key]
              tmp = Item(val)
              if tmp not in ITEMList:
                  ITEMList.append(tmp)
                  queue.append(tmp)
              item.next[key] = ITEMList.index(tmp)
...

LR1项目集族的构造函数LR1Parsing，计算出所有LR1项目集规范族，这里使用Item类表示每个项目集族，并用每个Item在ITEMLIST列表中的序号作为代表。

此处完全按照《编译原理》第145页的构造步骤进行，并用一个队列维护完成宽度优先搜索：

  • 首先计算预定义的开始项目集['<S>', ['.', '<start>'], {'#'}]的项目集闭包，将其加入队列中；
  • 当队列非空时，取出队列头item，将item内每个项目集内的圆点移动到下一位置，即求出当前项目集的下一项目集，这里为了去重，使用dict（map）建立符号到项目集的映射；
  • 遍历以上映射，计算项目集的闭包并构建item到每个项目集闭包的连接。

这里的内容和词法分析中nfa2dfa函数十分类似，区别在于：

  • LR1Parsing首先建立符号到项目集的映射，再遍历映射，完成闭包运算和项目集关系的连接；nfa2dfa直接计算闭包完成关系连接；
  • LR1Parsing并未如nfa2dfa那样使用闭包计算函数，而是使用项目集初始化一个Item类， 在Item类内部自动完成项目集的闭包运算。

运行测试

ACCEPT

输入代码如下时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# code.cpl
bool flag=True;
int main()
{
    for(int i=0;i<1;i^=1)
    {
        int b=1E9+7;
        break;
    }
    int k=-1.1e+1;
    k+=2;
    ++k;
    string _str="sd#f'\"s";
    #dsdss"sss
    while(k<5)
    {
        k=k+2;
        if(k==3&&5)
        {
            break;
        }

        if(k==4)
        {
            continue;
        }
        else
            k=8.1;
    }
}

输出：

1
ACCEPT

ERROR

输入代码如下时：

1
2
3
4
# code.cpl
int f$nc()
{
}

输出：

1
ERROR IN LEXICAL ANALYSIS

输入代码如下时：

1
2
3
# code.cpl
int func()
{

输出：

1
2
ERROR IN SYNTAX PARSER
ERROR

总结

写这个编译器是一个自我淬炼的过程。最开始看见要求时感觉是一个非常简单的项目，完成后回看那五百多行代码感觉也并无难点，但这一条本来应当非常简单的路却被我走的一波三折，最终堪堪完成任务，反复剖析，总结如下。

  • 没有认识到“教科书是最重要的参考资料”这一本质。写编译器之前，惯性地搜索了许多相关资料，想看看基本的思路是怎么样的。大致了解了思路后便直接上手，最后花了两个晚上写了一个靠手绘的NFA来识别的非自动式词法分析器和一个LL1的语法分析器。结果不言自明，只能从头再来。于是放弃了一切网络资料，老老实实照着书本上的算法一个个实现，终于完成了从正规式到NFA到DFA的真正的词法分析器和一个相较LL1难度加倍的LR1语法分析器。

  • 想着挑战自己，用python实现，却未想到正是python的部分陷阱让我苦苦挣扎。

    • 函数传值还是传引用？都不是。用python写过不少项目，一直以为python的函数参数是默认传值的，但在苦苦debug的过程中却发现有一部分参数传引用。查找资料才发现，其对于可变对象是传引用的，而对于不可变的对象却是传值的，这一项内容的疏忽，让我付出了很多时间作为代价；
    • 用字符串初始化set必须使用set literal。直接使用字符串初始化会被set分割成单独的字符，而向set直接添加字符串却是以整体形式存在。set和literal在我的漫长开发周期内被我反复忘记又反复被迫回忆，不断折磨着我；
    • 关于unhashable。最开始使用set类型作为主要工具，设置了大量的set套set的结构，直到错误信息提示set是一种unhashtable类型才罢休。unhashable？那将set改成hashable就是了，于是写了成员为set的添加了__hash__成员函数的类，直到发现其输出亦为hash值太难调试才停手。和hash的博弈持续了很久，最终还是采用了最为朴实的列表序号来替代set的方法解决了问题。

    使用python这样一种灵活的弱类型语言写程序总是让我产生一种反思维直觉的冲动，让我不由自主地尝试各类非典型的范式来解决普通问题，但往往问题要么没能解决要么十分低效，只能白费许多功夫，最终回到写C的时代，复现着各类朴实而高效的算法。这次的经历让我真正意识到了奇技淫巧往往不敌无锋重剑，朴实的招式才是高效编程的本源。

对我来说，每一门课设都达到最高要求是最低要求，但这一回未能实现，很是遗憾。现在想想，语义分析就像是一座云雾中的高山，我从未走入云雾中见识一番而只知其雄伟异常。上课时从未认真听过语义分析部分，直接导致这座高山的高度在我的心中被无限放大，让我失去了拨云驱雾迎难而上的雄心。